Present day digital imaging devices, such as televisions, digital cameras, and DVDs, offer advanced features that allow a viewer to adjust the image displayed. For instance, the viewer can adjust the color balance of the outputted image, the image's brightness and/or contrast, and the image's resolution. One feature that is popular is a zoom-in/out feature that allows the viewer to magnify or shrink the displayed image. Also popular are picture-in-picture (PIP) and picture-on-picture (POP) features where the display is divided into multiple windows and each window displays a different image signal (i.e., channel), or image. Here, the sizes of the windows can vary according to the viewer's preferences. Accordingly, the degree to which the image is magnified or reduced, i.e., the scaling factor, also varies.
To convert an input image of one resolution to an output image of another resolution, each target output pixel value is a weighted average of the input pixels within a convolution window surrounding the target output pixel. For most video standards, e.g., ITU-R BT.470, ITU-R BT.601, ITU-R BT.709, each pixel value of an input video signal is sampled according to a two-dimensional rectangular sampling grid. Similarly, for most display technologies currently in use, e.g., CRT, LCD, PDP, DMD, and LCoS, each pixel value of an input video signal is also displayed according to a two-dimensional rectangular grid on the screen of the display device. For these sampling and display systems operating in two-dimensional rectangular grids, separable two-dimensional filters are often used to reduce the implementation complexity of filtering functions in hardware, firmware, software, or a combination thereof.
For image scaling, i.e., image magnification or reduction, an image scaling system using separable two-dimensional filter kernels can include two one-dimensional image scalers in tandem, one operating in the vertical direction and the other operating in the horizontal direction. The image scaling functions in the vertical and horizontal directions are commutative, thus the order of the two one-dimensional image scalers is irrelevant to the output image. That is, an input image can be first magnified or reduced horizontally and then magnified or reduced vertically, or vice versa. By utilizing two one-dimensional image scalers in tandem, the amount of computation necessary to perform the scaling functions is greatly reduced, while maintaining substantially the same level of image quality as that of a non-separable circularly-symmetric filter.
Each one-dimensional image scaler, also referred to as a sampling rate converter, can convert an image by an arbitrary rational converting factor of L/M, where L and M are integers. Such conversion is typically implemented by up-sampling the input signal L times, low-pass filtering the up-sampled result, and then down-sampling the resultant signal M times. The up-sampling, also known as interpolation, can be performed by inserting L-1 zeros between every two input pixels and the down-sampling, also known as decimation, can be performed by discarding M-1 pixels for every M pixels to output one pixel. In order to avoid unnecessary multiplication with the inserted zeros and unnecessary computation for output pixels that are discarded through down-sampling, one or more finite impulse response (FIR) filters with time-varying coefficients, i.e., poly-phase filters, are employed. The time-varying coefficients vary according to the relative proximity, i.e., the phase, between the input and output pixels.
Two forms for implementing FIR filter structures include a direct-form FIR filter structure and a transposed-form FIR filter structure. The direct-form FIR filter structure operates at the output sampling rate, and computes each output pixel as a weighted average of the associated input pixels within its convolution window. The direct-form FIR filter structure requires buffering of the input pixels and is well suited for image enlargement. The transposed-form FIR filter structure operates at the input sampling rate, and distributes and accumulates each weighted input pixel among the affected output pixels within its convolution window. The transposed-form FIR filter structure requires buffering of the output pixels and is well suited for image reduction.
FIG. 1 illustrates a block diagram of a conventional one-dimensional sampling rate converter with rational converting factors that are ratios of two integers. Such a system is described in U.S. Pat. No. 4,020,332 entitled “Interpolation-Decimation Circuit for Increasing or Decreasing Digital Sampling Frequency” and in “Interpolation and Decimation of Digital Signals—A Tutorial Review,” Crochiere and Rabiner, Proceedings of the IEEE, March 1981, pp. 300-331. As shown in FIG. 1, the input pixel signal 10, x(n), is received by an L-times up-sampler 12. The output of the up-sampler 12, w(k), is transmitted to a low-pass finite-duration impulse response (FIR) filter 14 having an impulse response h(k). The output of the low-pass filter 14, v(k), is received by an M-times down-sampler 16 that produces at its output the converted signal 20, y(m).
The input pixel signal 10, x(n), with discrete Fourier transform X(ejω), is up-sampled by a factor of L by inserting L-1 zeros between every two values of x(n). The resulting signal w(k) is related to x(n) by
      w    ⁡          (      k      )        =      {                                                      x              ⁡                              (                                  k                  /                  L                                )                                      ,                                                                              for                ⁢                                                                  ⁢                k                            =              0                        ,                          ±              L                        ,                                          ±                2                            ⁢              L                        ,            …                                                            0            ,                                                otherwise            .                              
W(ejω), the discrete Fourier transform of w(k), contains the original baseband spectrum of X(ejω) along with replicas of X(ejω) centered at integer multiples of 2π/L. The up-sampled signal, w(k), is then low-pass filtered by the FIR filter 14 with impulse response h(k) and frequency response H(ejω). The FIR filter 14 interpolates the zero samples of w(k), removes the replica spectra, and limits the signal spectrum by a factor of M prior to down-sampling. According to the Nyquist criterion, to generate an ideal output signal 20, y(m), that is free of replica spectra, aliasing, and pass-band attenuation, the FIR filter 14 should have an ideal frequency response given by
      H    ⁡          (              ⅇ                  j          ⁢                                          ⁢          ω                    )        =      {                                        L            ,                                                              for              ⁢                                                          ⁢                                              ω                                                      ≤                          min              ⁡                              [                                                      π                    /                    L                                    ,                                      π                    /                    M                                                  ]                                                                                      0            ,                                                otherwise            .                              
Because such an ideal filter is not physically realizable, various approximations are made by filters that, while physically realizable, generally introduce replica spectra, aliasing, and pass-band attenuation. Finally, the interpolated signal v(k) is down-sampled by a factor of M and the converted output signal 20 y(m) isy(m)=v(Mm).
For implementing the filter impulse response h(k) with FIR structures having time-varying coefficients, i.e., poly-phase filters, the interpolated signal v(k) is related to the input signal x(n) by
                              v          ⁡                      (            k            )                          =                              ∑                          j              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              (                                  k                  -                  j                                )                                      ⁢                          w              ⁡                              (                j                )                                                                            =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              (                                  k                  -                  Lr                                )                                      ⁢                          x              ⁡                              (                r                )                                                        With a suitable change of variables, r=λMm/Lμ−n and modulo operations ((s))L=s−Lλs/Lμ, where λuμ denotes the closest integer less than or equal to u, the converted output signal 20, y(m), is related to the input signal 10, x(n), by
                              y          ⁡                      (            m            )                          =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              (                                  Mm                  -                  Lr                                )                                      ⁢                          x              ⁡                              (                r                )                                                                            =                              ∑                          n              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              [                                  Mm                  -                                      L                    ⁡                                          (                                                                        λ                          ⁢                                                                                                          ⁢                                                      Mm                            /                            L                                                    ⁢                                                                                                          ⁢                          μ                                                -                        n                                            )                                                                      ]                                      ⁢                          x              ⁡                              (                                                      λ                    ⁢                                                                                  ⁢                                          Mm                      /                      L                                        ⁢                                                                                  ⁢                    μ                                    -                  n                                )                                                                            =                              ∑                          n              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              (                                  Mm                  -                                      L                    ⁢                                                                                  ⁢                    λ                    ⁢                                                                                  ⁢                                          Mm                      /                      L                                        ⁢                                                                                  ⁢                    μ                                    +                                      L                    ⁢                                                                                  ⁢                    n                                                  )                                      ⁢                          x              ⁡                              (                                                      λ                    ⁢                                                                                  ⁢                                          Mm                      /                      L                                        ⁢                                                                                  ⁢                    μ                                    -                  n                                )                                                                            =                              ∑                          n              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              [                                                                            (                                              (                        Mm                        )                                            )                                        L                                    +                                      L                    ⁢                                                                                  ⁢                    n                                                  ]                                      ⁢                          x              ⁡                              (                                                      λ                    ⁢                                                                                  ⁢                                          Mm                      /                      L                                        ⁢                                                                                  ⁢                    μ                                    -                  n                                )                                                                            =                              ∑                          n              =                              -                ∞                                      ∞                    ⁢                                                    g                m                            ⁡                              (                n                )                                      ⁢                          x              ⁡                              (                                                      λ                    ⁢                                                                                  ⁢                                          Mm                      /                      L                                        ⁢                                                                                  ⁢                    μ                                    -                  n                                )                                                        where the poly-phase filter responses gm(n) are defined asgm(n)=h[((Mm))L+Ln], for all m and all n
If the length, N, of the FIR filter impulse response h(k) is assumed to be a multiple of L, i.e., N=KL, where K is an integer, then all of the poly-phase filter responses gm(n) contain K filter coefficients for n=0, 1, . . . , K−1. Furthermore, gm(n) is periodic in m with period L, so thatgm(n)=g((m))L(n), for all m and all nTherefore, the converted output signal 20, y(m), can be expressed as
      y    ⁡          (      m      )        =            ∑              n        =        0                    K        -        1              ⁢                            g                                    (                              (                m                )                            )                        L                          ⁡                  (          n          )                    ⁢              x        ⁡                  (                                    λ              ⁢                                                          ⁢                              Mm                /                L                            ⁢                                                          ⁢              μ                        -            n                    )                    where each output pixel y(m) 20 can be calculated as a weighted sum of K consecutive input samples 10, x(n), starting at index λMm/Lμ and going backward in n. The above equation relating the converted output signal 20, y(m), and the input signal 10, x(n), can be readily implemented as a single-stage direct-form FIR architecture with poly-phase filter responses as is well known to those skilled in the art.
Similarly, with another suitable change of variables, m=φLr/Mκ+m ! φLr/Mκ and modulo operations ((S))M=s+Mφ!s/Mκ, where φuκ denotes the closest integer greater than or equal to u, the converted output signal 20, y(m), is related to the input signal 10, x(n), by
                              y          ⁡                      (            m            )                          =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              (                                  Mm                  -                  Lr                                )                                      ⁢                          x              ⁡                              (                r                )                                                                            =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              [                                                      M                    ⁡                                          (                                                                        φ                          ⁢                                                                                                          ⁢                                                      Lr                            /                            M                                                    ⁢                                                                                                          ⁢                          κ                                                +                        m                        -                                                  φ                          ⁢                                                                                                          ⁢                                                      Lr                            /                            M                                                    ⁢                                                                                                          ⁢                          κ                                                                    )                                                        -                  Lr                                ]                                      ⁢                          x              ⁡                              (                r                )                                                                            =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              [                                                      M                    ⁢                                                                                  ⁢                    φ                    ⁢                                                                                  ⁢                                          Lr                      /                      M                                        ⁢                                                                                  ⁢                    κ                                    -                  Lr                  +                                      M                    ⁡                                          (                                              m                        -                                                  φ                          ⁢                                                                                                          ⁢                                                      Lr                            /                            M                                                    ⁢                                                                                                          ⁢                          κ                                                                    )                                                                      ]                                      ⁢                          x              ⁡                              (                r                )                                                                            =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                    h              ⁡                              [                                                                            (                                              (                                                  !                          Lr                                                )                                            )                                        M                                    +                                      M                    ⁡                                          (                                              m                        -                                                  φ                          ⁢                                                                                                          ⁢                                                      Lr                            /                            M                                                    ⁢                                                                                                          ⁢                          κ                                                                    )                                                                      ]                                      ⁢                          x              ⁡                              (                r                )                                                                            =                              ∑                          r              =                              -                ∞                                      ∞                    ⁢                                                    f                r                            ⁡                              (                                  m                  -                                      φ                    ⁢                                                                                  ⁢                                          Lr                      /                      M                                        ⁢                                                                                  ⁢                    κ                                                  )                                      ⁢                          x              ⁡                              (                r                )                                                        where the poly-phase filter responses fr(n) are defined asfr(n)=h[((!Lr))M+Mn], for all r and all nIf the length, N, of the FIR filter impulse response h(k) is assumed to be a multiple of M, i.e., N=KM, where K is an integer, then all of the poly-phase filter responses fr(n) contain K filter coefficients for n=0, 1, . . . , K−1. Furthermore, fr(n) is periodic in r with period M, so thatfr(n)=f((r))M(n), for all r and all nTherefore, the converted output signal 20, y(m), can be expressed as
      y    ⁡          (      m      )        =            ∑                        ⌈                      Lr            /            M                    ⌉                =                  m          -          k          +          1                    m        ⁢                            f                                    (                              (                r                )                            )                        M                          ⁡                  (                      m            -                          φ              ⁢                                                          ⁢                              Lr                /                M                            ⁢                                                          ⁢              κ                                )                    ⁢              x        ⁡                  (          r          )                    where each input pixel 10, x(r), contributes to K consecutive output pixels of 20, y(m), starting at index φLr/Mκ and going forward in m. The above equation relating the converted output pixels 20, y(m), and the input pixels 10, x(n), can be readily implemented as a single-stage transposed-form FIR architecture with poly-phase filter responses as is well known to those skilled in the art.
The FIR filter 14 having an impulse response h(k) described above must have frequency response H(eiω) with a cutoff frequency of π divided by the larger of L or M. For large image magnification factors, i.e., L/M>>1; L>>M, or larger image reduction factors, i.e., L/M<<1; L<<M, one of L or M tends to be much larger than the other, resulting in a narrow-band FIR filter. According to digital filter design principles known in the art, the number of coefficients of an FIR filter 14, and thus the size of pixel buffer memory and the number of multipliers and adders, is inversely proportional to its bandwidth. Therefore, the FIR filter 14 tends to have a large number of coefficients for large image magnification or reduction factors.
For example, in a single-stage direct-form FIR filter structure, the number of filter coefficients, i.e., K=N/L, of the poly-phase filter responses gm(n) tends to increase as the image reduction factor increases. As the number of filter coefficients increases, the size of the input pixel buffer, as well as the number of multipliers and adders, must also increase. Similarly, in a single-stage transposed-form FIR architecture, the number of filter coefficients, i.e., K=N/M, of the poly-phase filter responses fr(n) tends to increase as the image magnification factor increases, causing the need for larger sized output pixel buffer memory and more multipliers and adders.
One approach to dealing with a large number of filter coefficients includes implementing multi-stage FIR filter structures. While multi-stage direct-form or transposed-form FIR filter structures can provide a means to reduce the total coefficients required for each FIR filter structure for large image magnification or reduction factors, the additional FIR stages make the filter structures and system clocks more complicated and thus increase system complexity and cost.
Accordingly, it is desirable to provide a method and apparatus that is suitable for both large image magnification and large image reduction factors. The method and apparatus should be cost effective and computationally efficient. In addition, the method and apparatus should produce an output image substantially without aliasing, moiré, and other visual artifacts over a wide range of image magnification and reduction factors.